Search for: All records

An ordered graph is a graph with a linear ordering on its vertices. The online Ramsey game for ordered graphs $$G$$ and $$H$$ is played on an infinite sequence of vertices; on each turn, Builder draws an edge between two vertices, and Painter colors it red or blue. Builder tries to create a red $$G$$ or a blue $$H$$ as quickly as possible, while Painter wants the opposite. The online ordered Ramsey number $$r_o(G,H)$$ is the number of turns the game lasts with optimal play. In this paper, we consider the behavior of $$r_o(G,P_n)$$ for fixed $$G$$, where $$P_n$$ is the monotone ordered path. We prove an $$O(n \log n)$$ bound on $$r_o(G,P_n)$$ for all $$G$$ and an $O(n)$ bound when $$G$$ is $$3$$-ichromatic; we partially classify graphs $$G$$ with $$r_o(G,P_n) = n + O(1)$$. Many of these results extend to $$r_o(G,C_n)$$, where $$C_n$$ is an ordered cycle obtained from $$P_n$$ by adding one edge. 

Abstract LetXbe ann-element point set in thek-dimensional unit cube$$[0,1]^k$$ ${[0,1]}^k$where$$k \ge 2$$ $k\ge 2$. According to an old result of Bollobás and Meir (Oper Res Lett 11:19–21, 1992) , there exists a cycle (tour)$$x_1, x_2, \ldots , x_n$$ $x_1,x_2,\dots ,x_n$through thenpoints, such that$$\left( \sum _{i=1}^n |x_i - x_{i+1}|^k \right) ^{1/k} \le c_k$$ ${\left({\sum }_{i=1}^n,{|x_i-x_{i+1}|}^k\right)}^{1/k}\le c_k$, where$$|x-y|$$ $|x-y|$is the Euclidean distance betweenxandy, and$$c_k$$ $c_k$is an absolute constant that depends only onk, where$$x_{n+1} \equiv x_1$$ $x_{n+1}\equiv x_1$. From the other direction, for every$$k \ge 2$$ $k\ge 2$and$$n \ge 2$$ $n\ge 2$, there existnpoints in$$[0,1]^k$$ ${[0,1]}^k$, such that their shortest tour satisfies$$\left( \sum _{i=1}^n |x_i - x_{i+1}|^k \right) ^{1/k} = 2^{1/k} \cdot \sqrt{k}$$ ${\left({\sum }_{i=1}^n,{|x_i-x_{i+1}|}^k\right)}^{1/k}=2^{1/k}·\sqrt{k}$. For the plane, the best constant is$$c_2=2$$ $c_2=2$and this is the only exact value known. Bollobás and Meir showed that one can take$$c_k = 9 \left( \frac{2}{3} \right) ^{1/k} \cdot \sqrt{k}$$ $c_k=9{\left(\frac{2}{3}\right)}^{1/k}·\sqrt{k}$for every$$k \ge 3$$ $k\ge 3$and conjectured that the best constant is$$c_k = 2^{1/k} \cdot \sqrt{k}$$ $c_k=2^{1/k}·\sqrt{k}$, for every$$k \ge 2$$ $k\ge 2$. Here we significantly improve the upper bound and show that one can take$$c_k = 3 \sqrt{5} \left( \frac{2}{3} \right) ^{1/k} \cdot \sqrt{k}$$ $c_k=3\sqrt{5}{\left(\frac{2}{3}\right)}^{1/k}·\sqrt{k}$or$$c_k = 2.91 \sqrt{k} \ (1+o_k(1))$$ $c_k=2.91\sqrt{k}(1+o_k\left(1\right))$. Our bounds are constructive. We also show that$$c_3 \ge 2^{7/6}$$ $c_3\ge 2^{7/6}$, which disproves the conjecture for$$k=3$$ $k=3$. Connections to matching problems, power assignment problems, related problems, including algorithms, are discussed in this context. A slightly revised version of the Bollobás–Meir conjecture is proposed. 

Abstract The Erdős–Simonovits stability theorem states that for all ε > 0 there exists α > 0 such that if G is a K r+ 1 -free graph on n vertices with e ( G ) > ex( n , K r +1 )– α n 2 , then one can remove εn 2 edges from G to obtain an r -partite graph. Füredi gave a short proof that one can choose α = ε . We give a bound for the relationship of α and ε which is asymptotically sharp as ε → 0.